import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Leetcode {
}
//leetcode:904.:水果成篮
//哈希表+滑动窗口
class Solution1 {
    public int totalFruit(int[] fruits) {
        //创建哈希表
        Map<Integer,Integer> hash = new HashMap<>();
        int ret = 0;
        for(int left = 0,right = 0;right < fruits.length;right++){
            int in = fruits[right];//得到对应位置的水果种类
            hash.put(in,hash.getOrDefault(in,0)+1);//如果存在直接让对应的数量加一，不存在从0开始加一
            while(hash.size() > 2){//如果哈希表中水果的种类大于两种了
                int out = fruits[left];//就从左开始去掉
                hash.put(out,hash.get(out)-1);//同时让要删除种类的数量减一
                if(hash.get(out) == 0){//如果数量等于0了，就代表这类的水果不存在了，那么就在哈希表中移除这类水果的代表
                    hash.remove(out);
                }
                left++;//每去掉一个水果，就让向右移动
            }
            ret = Math.max(ret,right-left+1);//如果水果的种类等于2时，去判断每个等于2的数量最大值
        }
        return ret;
    }
}
//leetcode:438:找到字符串中所有字母异位词
//哈希表+滑动窗口
class Solution2 {
    public List<Integer> findAnagrams(String ss, String pp) {//为了方便进行的更改
        //创建一个链表用于返回
        List<Integer> list = new ArrayList<>();
        //将字符串转变成字符数组
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        //创建能存储26个字母的的数组，模拟哈希表
        int[] hash1 = new int[26];
        //将p中的所有元素放到hash1中，每有一个相同的元素就让它对应的加一，实现哈希表
        for(char ch : p){
            hash1[ch-'a']++;
        }
        //创建hash2
        int[] hash2 = new int[26];
        int m = p.length;//得到异位词的长度
        for(int left = 0,right = 0,count = 0;right < s.length;right++){
            //遍历数组s将他的元素放到hash2中
            char c = s[right];
            hash2[c-'a']++;
            //如果我们hash2对应的元素的个数小于等于hash1对应元素的个数
            if(hash2[c-'a'] <= hash1[c-'a']){
                count++;//就让我们有效单词的个数加一
            }
            //如果我们移动的位置超过了我们要得到异位词的长度就要让left往右走
            if(right-left+1 > m){
                char out = s[left++];
                //如果在hash1中存在并且个数小于等于hash1对应元素的个数，就要让有效元素个数减一
                if(hash2[out - 'a']-- <= hash1[out-'a']){
                    count--;
                }
            }
            //如果有效长度等于我们的p数组长度，就将此时left位置传入链表当中
            if(count == m){
                list.add(left);
            }
        }
        return list;
    }
}


